package algorithm.node;

import ch.qos.logback.core.pattern.FormatInfo;
import com.google.errorprone.annotations.Var;

import java.lang.reflect.Array;
import java.util.*;

/**
 * 证明一个单链表是回文链表
 *
 * @author csp 2021-12-05
 */
public class Code01_PalindromeLinkedList {

    private static class ListNode {
        private ListNode next;
        int value;

        public ListNode(int value) {
            super();
            this.value = value;
            Arrays.sort(new Integer[10], new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return 0;
                }
            });
        }




    }

    //

    /**
     *  解决的方法有两种，
     *  一种是将链表进行翻转（这里可以使用递归来解决）然后翻转后的后半部分与链表的前半部分进行比较来进行判断，
     *  第二种是将先找到链表的中间位置，这里可以使用快慢指针指针来进行，快指针一次走一步，慢指针一次走两步，
     *  那么等到快指针走到末尾的时候那么慢指针的位置是链表的中间位置，在求出中间位置的时候对慢指针指向的元素进行压栈，
     *  等到循环结束那么堆栈里面存储的是链表的前半部分的元素，这里需要注意的时候需要在循环中判断链表的节点是奇数还是偶数，
     *  假如是奇数那么慢指针应该再走一步，因为判断回文假如是奇数的节点的话中间那个元素是不用进行判断的
     *
     *  扩展（只用有限变量。空间复杂度O(1)）
     *
     * ————————————————
     * @param node
     */
    public static void palindromeLinkedList(LinkedList node) {

    }

    // 递归实现中间节点后续的链表反转
    public static ListNode reverse(ListNode head) {
        if (head.next == null) return head;
        ListNode last = reverse(head.next);
        //执行到这里时候已经把第二个到最后一个都反转完了；
        last.next.next = head;//第二个节点的next反转连接到第一个
        head.next = null;//第一个链接到null；
        return last;
    }

    //迭代方式反转链表
    public ListNode reverse2(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode tmp = null;
        ListNode pre = null;
        while (head.next != null) {
            // null,  1,  2;
            tmp = head.next;//2
            head.next = pre;
            pre = head;
            head = tmp;
        }
        head.next = pre;
        return head;
    }
    //
    public static void main(String[] args) {
    }
}
